Хроматическое число


Хроматическое число

Хроматическое число [chro­matic number] — число, характеризующее количество несмежных вершин графа. Если пометить все вершины графа р цветами (отсюда и термин“хроматическое”) и при этом никакие две смежные вершины не будут окрашены одинаково, то такой граф называется хроматическим порядка р . Минимальное число р, при котором граф является хроматическим порядка р, называется хроматическим числом данного графа. Оно находится с помощью аналитического метода, основанного на обычных приемах линейного программирования.


Экономико-математический словарь: Словарь современной экономической науки. — М.: Дело. . 2003.

Смотреть что такое "Хроматическое число" в других словарях:

  • хроматическое число — Число, характеризующее количество несмежных вершин графа. Если пометить все вершины графа р цветами (отсюда и термин“хроматическое”) и при этом никакие две смежные вершины не будут окрашены одинаково, то такой граф называется хроматическим… …   Справочник технического переводчика

  • Хроматическое число — 3 раскраска графа Петерсена Хроматическое число графа G  минимальное число цветов, в которые можно раскрасить вершины …   Википедия

  • Раскраска графа — 3 раскраска графа Петерсена Хроматическое число графа G  минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G). Содержание 1 Определение …   Википедия

  • Раскрашиваемый граф — 3 раскраска графа Петерсена Хроматическое число графа G  минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G). Содержание 1 Определение …   Википедия

  • Хроматический граф — 3 раскраска графа Петерсена Хроматическое число графа G  минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G). Содержание 1 Определение …   Википедия

  • Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С …   Википедия

  • Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) …   Википедия

  • Инвариант графа — в теории графов  некоторое обычно числовое значение или упорядоченный набор значений (хэш функция), характеризующее структуру графа и не зависящее от способа обозначения вершин или графического изображения графа. Играет важную роль при… …   Википедия

  • Нерешённые проблемы математики — Нерешённые проблемы (или Открытые проблемы)  проблемы, которые рассматривались математиками, но до сих пор не решены. Часто принимают форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна практика… …   Википедия

  • Открытые математические проблемы — Открытые (нерешённые) математические проблемы  проблемы, которые рассматривались математиками, но до сих пор не решены. Часто имеют форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.